package cym;

public class HeapSort {

    public static void sort(int[] r) {
        int n = r.length;
        int temp;
        for (int i = n / 2 - 1; i >= 0; i--) {//创建堆
            sift(r, i, n);
        }
        for (int i = n - 1; i > 0; i--) {//每趟将最小值交换到后面，再调整成堆
            temp = r[0];
            r[0] = r[i];
            r[i] = temp;
            sift(r, 0, i);
        }
    }

    //将以low为根的子树调整成小顶堆，low、high是序列下界和上界
    public static void sift(int[] r, int low, int high) {
        int i = low;                               //子树的根
        int j = 2 * i + 1;                         //j为i结点的左孩子
        int temp = r[i];
        while (j < high) {
            if (j < high - 1 && r[j] > r[j + 1]) {
                j++; //数组元素比较,j为左右孩子的较小者
            }
            if (temp > r[j]) { //若父结点值较大
                r[i] = r[j];           //孩子结点中的较小值上移
                //向下处理
                i = j;
                j = 2 * i + 1;
            } else {
                j = high + 1;          //退出循环
            }
        }
        r[i] = temp;                   //找到根节点的位置，当前子树的原根值调整后的位置
    }

    public static void display(int[] r) {
        for (int item : r) {
            System.out.print(item + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int[] r = new int[]{3, 5, 5, 4, 120, 43, 1, 76, 78, 12, 346};
        HeapSort.sort(r);
        HeapSort.display(r);
    }

}
